SPOJ694 Distinct Substrings

Posted on | In , ,

给定一个字符串，求该字符串含有的本质不同的子串数量。$(|S|\le 2·10^4)$

题解

每个子串都是原字符串后缀的前缀，考虑任意一个后缀${\rm suffix}(i)$，对子串的贡献为$len-i+1$。在后缀数组中${\rm height}(i)$表示排名第i小和第i-1小的后缀的最长公共前缀，其产生的贡献即为${\rm height}(i)$，减去这部分即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
using namespace std;


//sa:字典序中排第i位的起始位置在str中第sa[i]  sa[1~n]为有效值,取值范围为[0,len-1]
//rank:就是str第i个位置的后缀是在字典序排第几 rank[0~n-1]为有效值
//height：字典序排i和i-1的后缀的最长公共前缀  height[2~n]为有效值，第二个到最后一个

const int maxn = 2e5+5;//开总串长度，不要忘记连接符
int wa[maxn],wb[maxn],wsf[maxn],wv[maxn],sa[maxn],rk[maxn],ht[maxn],ns[maxn];
char hs[maxn];

int cmp(int *r,int a,int b,int k)
{
    return r[a]==r[b]&&r[a+k]==r[b+k];
}

void getsa(int *r,int *sa,int n,int m)  //n为添加0后的总长
{
    int i,j,p,*x=wa,*y=wb,*t;
    for(i=0; i<m; i++)  wsf[i]=0;
    for(i=0; i<=n; i++)  wsf[x[i]=r[i]]++;
    for(i=1; i<m; i++)  wsf[i]+=wsf[i-1];
    for(i=n; i>=0; i--)  sa[--wsf[x[i]]]=i;
    p=1;
    j=1;
    for(; p<=n; j*=2,m=p)
    {
        for(p=0,i=n+1-j; i<=n; i++)  y[p++]=i;
        for(i=0; i<=n; i++)  if(sa[i]>=j)  y[p++]=sa[i]-j;
        for(i=0; i<=n; i++)  wv[i]=x[y[i]];
        for(i=0; i<m; i++)  wsf[i]=0;
        for(i=0; i<=n; i++)  wsf[wv[i]]++;
        for(i=1; i<m; i++)  wsf[i]+=wsf[i-1];
        for(i=n; i>=0; i--)  sa[--wsf[wv[i]]]=y[i];
        t=x;  x=y;  y=t;
        x[sa[0]]=0;
        for(p=1,i=1; i<=n; i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)? p-1:p++;
    }
}

void getht(int *r,int n) //n为添加0后的总长
{
    int i,j,k=0;
    for(i=1; i<=n; i++)  rk[sa[i]]=i;
    for(i=0; i<n; i++)
    {
        if(k)k--;
        else k=0;
        j=sa[rk[i]-1];
        while(r[i+k]==r[j+k]) k++;
        ht[rk[i]]=k;
    }
}


int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%s", hs);
        int len=strlen(hs);
        for(int i=0;i<len;i++)  ns[i]=int(hs[i]);
        ns[len]=0;
        getsa(ns, sa, len, 256);
        getht(ns, len);
        int ans=len*(len+1)/2;
        for(int i=2;i<=len;i++)
            ans-=ht[i];
        printf("%d\n", ans);
    }
}